//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：n = 4
//输出：2
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。 
// 
// 
// 
// Related Topics 回溯算法 
// 👍 269 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

public class NQueensIi {
    public static void main(String[] args) {
        Solution solution = new NQueensIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private int[] visitI;
        private int[] visitJ;
        private int count;
        public int totalNQueens(int n) {
            visitI=new int[n];
            visitJ=new int[n];
            dfs(n);
            return count;

        }
        public void dfs(int n ){
            if (sum(visitJ)==n){
                count++;
            }
            for (int ii=0;ii<n;ii++){
                for (int jj=0;jj<n;jj++){
                    if (visitI[ii]==1 || visitJ[jj]==1){
                        continue;
                    }
                    visitJ[jj]=1;
                    visitI[ii]=1;
                    dfs(n);
                    visitJ[jj]=0;
                    visitI[ii]=0;
                }
            }
        }
        public int sum(int[] nums){
            int count =0;
            for (int num:nums){
                count+=num;
            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}